/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
export var deleteNode = function (root, key) {
  if (!root) return root
  let parent = null
  let deleted = root
  let isLeft = false
  while (deleted && deleted.val !== key) {
    parent = deleted
    isLeft = deleted.val > key
    deleted = deleted.val > key ? deleted.left : deleted.right
  }
  if (deleted === null) return root
  if (deleted.left === null && deleted.right === null) {
    if (parent === null) return null
    setNodeToParent(null, parent, isLeft)
    return root
  }
  if (deleted.left === null) {
    if (parent === null) return deleted.right
    setNodeToParent(deleted.right, parent, isLeft)
    return root
  }
  if (deleted.right === null) {
    if (parent === null) return deleted.left
    setNodeToParent(deleted.left, parent, isLeft)
    return root
  }

  // 左右子树都不为空
  let minNode = deleted.left
  // 找到最右叶子节点
  let rightmost = minNode
  while (rightmost.right) {
    rightmost = rightmost.right
  }
  rightmost.right = deleted.right
  if (parent === null) return minNode
  setNodeToParent(minNode, parent, isLeft)
  return root
}

function setNodeToParent(node, parent, isLeft) {
  if (isLeft) {
    parent.left = node
  } else {
    parent.right = node
  }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * 递归
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
export var deleteNode2 = function (root, key) {
  if (!root) return root
  if (key > root.val) {
    root.right = deleteNode2(root.right, key)
    return root
  } else if (key < root.val) {
    root.left = deleteNode2(root.left, key)
    return root
  }
  if (!root.left && !root.right) return null
  if (!root.left) return root.right
  if (!root.right) return root.left
  let rightmost = root.left
  while (rightmost.right) {
    rightmost = rightmost.right
  }
  rightmost.right = root.right
  return root.left
}
